#ifndef AI_MONTE_CARLO_H
#define AI_MONTE_CARLO_H



#include "ai.h"



/** @brief AI state, that is used to build a search tree
*
*   \image html ai_monte_carlo.jpeg
*/
class ai_states_node_mc
{

public:

	/**	@brief Constructor, that connects ai_game_state to states tree
	*	@param p parrent of the node
	*	@param s ai_game_state to be connected to the parent
	*/
	ai_states_node_mc( ai_states_node_mc* p, ai_game_state* s );

	//! @brief Destructor deletes all its children
	~ai_states_node_mc();

	//! algorithm owner's score
	double my_score;
	//! current player's score
	double current_score;
	//! previous player's score
	double prev_score;
	//! if the node is on path, that is expanded to the end
	bool expanded;

	//! parent of this node
	ai_states_node_mc* parent;
	//! parent of this node at the end of previous level
	ai_states_node_mc* level_parent;
	//! list of children
	list< ai_states_node_mc* >* children;
	//! list of children at the beginning of next level
	list< ai_states_node_mc* >* level_children;
	//! the ai_game_state
	ai_game_state* state;
	//! actual depth, where the node is
	int depth;
};



/** @brief The main algorithm class.
*
*	This algorithm is based on search of state space and generating state tree. The whole state space is being searched to depth set in
*	parameters::ai_parameters[ "MONTE_CARLO" ][ "depth" ]. Depth 1 means, that the state space will be searched to the end of first player's turn.
*	Depth 2 means, that it will be searched to the end of next player's turn and so on.
*
*	At the beginning, the given game_state is used to create the root of whole tree composed of ai_states_node_mc. For each ation, that can be done
*	on the node, the child is added. If the node will, or will not be expanded depends on some random events and is handled by
*	monte_calo_algorithm::get_list_to_expand( list< ai_states_node_mc* >* all_children ). It generates some random numbers, that are used to equations
*	and together with some parameters it will compute the final score for each children and tahe only some of them with the highest score. The number
*	of nodes to expand is defined in parameters::ai_parameters[ "MONTE_CARLO" ][ "width" ]. When the child contains "NXT" command, it is connected
*	to ai_states_node_mc::level_parent. Duplicities are excluded using monte_carlo_algorithm::searched_states_list.

*	At the end of search, we find the best commands. We assume, that every players is maximising his score and thinks one round to future, so we
*	search only states in search_algorithm::state_levels and when the enemy is on turn, we find for each child the one with maximum score and we
*	assume, that he will choose this state. The previous player is trying to avoid this player to maximise his score, so he will choose the state,
*	where his worst predictabe score is highest nad so on. When we get to root, we find the state with highest score for us and find commands, how
*	to get there.
*
*   \image html ai_monte_carlo.jpeg
*/
class monte_carlo_algorithm: public algorithm
{

public:

	//! @brief Constructor only assignes the name
	monte_carlo_algorithm()
	{
		name = "Monte Carlo algorithm";
		search_tree = 0;
		state_levels = 0;
		searched_states_list = 0;
	};

	//! @brief Destructor cleans all staff
	~monte_carlo_algorithm()
	{
		if ( search_tree != 0 )
			delete search_tree;
		if ( state_levels != 0 )
			delete state_levels;
		if ( searched_states_list != 0 )
			delete searched_states_list;
	};

	/** @brief	Registrating function (adds ai algorithm to map)
	*/
	static void register_me()
	{
		register_metpl< monte_carlo_algorithm >();
	};

	/** @brief	Cloning function for init purposes
	*	@return	clone of the algorithm
	*/
	virtual algorithm* clone()
	{
		monte_carlo_algorithm* cl = clonetpl< monte_carlo_algorithm >();
		return cl;
	};

	/** @brief Function called at the beginning of buy
	*	@param gs current game state
	*/
	void get_buy_commands( const game_state* gs );
	/** @brief Function called at the beginning of every turn
	*	@param gs current game state
	*/
	void get_commands( const game_state* gs );


private:

	/**	@brief Expands given state and connects all children
	*	@param state_node node to expand, constraint: state_node != 0
	*/
	void search_state( ai_states_node_mc* state_node );

	//! pointer to the root of the tree
	ai_states_node_mc* search_tree;

	/** @brief Adds state to list of searched states
	*	@param state game state to add, constraint: state != 0
	*/
	void add_to_list( game_state* state );
	/** @brief	Checks if the state was already searched
	*	@param	state game state to check, constraint: state != 0
	*	@return true if state is already in list and was searched, else false
	*/
	bool is_in_list( game_state* state );

	//! map of searched states, indexed by hash, one field contains list of states with same hash
	map< unsigned long long int, list< game_state* > >* searched_states_list;

	//! vector of lists, where are all states in one depth, that are on the end of turn
	vector< list< ai_states_node_mc* > >* state_levels;

	/** @brief	Finds form list of nodes the one with highest score for algorithm owner
	*	@param	node_list list where to find for the node
	*	@return	node with the highest score
	*/
	ai_states_node_mc* find_max_score_me( list< ai_states_node_mc* >* node_list );
	/** @brief	Finds form list of nodes the one with highest score for current player
	*	@param	node_list list where to find for the node
	*	@return	node with the highest score
	*/
	ai_states_node_mc* find_max_score_curr( list< ai_states_node_mc* >* node_list );
	/** @brief	Finds form list of nodes the one with highest score for previous player
	*	@param	node_list list where to find for the node
	*	@return	node with the highest score
	*/
	ai_states_node_mc* find_max_score_prev( list< ai_states_node_mc* >* node_list );

	/** @brief	Rates game state (faster, than game_state_estimate function)
	*	@param	state ai_game_state to rate, constraint: state != 0
	*	@return game state rating
	*/
	double rate_state( ai_game_state* state );

	/** @brief	From list select those, that will be expanded
	*	@param	all_children list, where to search for nodes to expand
	*	@return list of nodes to expand
	*/
	list< ai_states_node_mc* >* get_list_to_expand( list< ai_states_node_mc* >* all_children );

	/** @brief Inserts pair of node and score to sorted list of these pairs
	*	@param slist list, where to insert pair
	*	@param sunit pair to insert
	*/
	void insert_to_sorted_list( list< pair< ai_states_node_mc*, double > >& slist, pair< ai_states_node_mc*, double >& sunit );

	//! remaining nodes to search
	unsigned int nodes_to_search;
	//! searched nodes
	unsigned int searched_nodes;

	//! given state - never changed
	const game_state* original_state;

};



#endif